1. Field of the Invention
The invention concerns a method for processing data involving modular exponentiation, and a related device.
2. Description of the Related Art
Modular exponentiation calculations are often used in cryptographic algorithms and in this context generally introduce a secret, that is to say a number stored by the device that uses the cryptographic algorithm and that is not accessible from the exterior.
The steps that implement the modular exponentiation are particularly subject to attacks by malicious persons; these may be error generation attacks (in particular of the DFA (Differential Fault Analysis) type) or attacks by analysis of the current consumption of the device that uses the algorithm (of the SPA (Statistical Power Analysis) or DPA (Differential Power Analysis) type).
Attempts have therefore been made to protect these steps, in particular in the case where the secret to be protected corresponds to the exponent used in the modular exponentiation.
Thus if a “square-and-multiply” type algorithm is used in which a variable is updated by multiplication for each bit of the exponent having the value 1 (and for those bits only), attempts have been made to render the process symmetrical, for example by effecting a snare multiplication if the bit of the exponent has the value 0, with the aim of countering attacks by measurement of current (sometimes called SPA attacks) or by measurement of time (“timing attacks”).
Starting from this general idea, various algorithms protected against SPA type attacks have been developed, such as that described in the paper “The Montgomery Powering Ladder”, B. S. Kaliski Jr., C. Q. Koc and C. Paar, “Cryptographic Hardware and Embedded Systems”—CHES 2002, pages 291-302.
Attempts have also been made to protect cryptographic algorithms, including those using modular exponentiation, from error generation attacks, by means of which an attacker attempts to deduce information on the internal operation of the device that uses the cryptographic method by generating a malfunction within that process.
One solution widely used to combat this latter type of attack consists in duplicating the calculations effected in order to verify that both iterations of the same calculation give the same result, which generally tends to prove that no error has occurred during their execution. However, this solution entails doubling the calculation time for each operation to be protected (not to mention the necessary subsequent verification step), which is naturally not desirable.
To remedy this problem, patent application WO 98/52319 proposes, when the Chinese Remainder Theorem (CRT) is used, to exploit the assumed identity of two values each obtained from one of the branches of the algorithm using this theorem to verify the a priori error-free execution of the algorithm in its two branches.
This solution, which exploits a particular feature of applications using the Chinese Remainder Theorem, is not applicable to other types of implementation, however. It should further be mentioned on this subject that using the Chinese Remainder Theorem involves knowing the decomposition into prime numbers p, q of the public module n=p·q.
Finally, this solution effects a verification by means of data employed at an intermediate stage of the process, and therefore cannot verify error-free operation at all points of the process, as the designer might wish: for example, this technique cannot protect the process in the case of error generation attacks upon recombination of the result obtained by each of the branches of the algorithm.